package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-19 10:03
 * @description: Functions of this class is
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 * 官方解法：(动态规划算法)
 * public int trap(int[] height) {
 *     int sum = 0;
 *     int[] max_left = new int[height.length];
 *     int[] max_right = new int[height.length];
 *
 *     for (int i = 1; i < height.length - 1; i++) {
 *         max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
 *     }
 *     for (int i = height.length - 2; i >= 0; i--) {
 *         max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
 *     }
 *     for (int i = 1; i < height.length - 1; i++) {
 *         int min = Math.min(max_left[i], max_right[i]);
 *         if (min > height[i]) {
 *             sum = sum + (min - height[i]);
 *         }
 *     }
 *     return sum;
 * }
 *
 **/
public class NoNo接雨水and动态规划解法联动除自身的乘积 {
    public static void main(String args[]){
        // 1 0 2 5 3 height[]
        //maxleft
        System.out.println(trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
    }
    public static int trap(int[] height) {
        //按照每一列每一列来求
        int ans=0;
        int maxLeft[]=new int[height.length];
        int maxRight[]=new int[height.length];

        for(int i=1;i<height.length;i++){//分别找到每一列左边最高的那一列
            maxLeft[i]=Math.max(height[i-1],maxLeft[i-1]);
        }
        for(int i=height.length-2;i>=0;i--){//分别找到每一列右边最高的那一列
            maxRight[i]=Math.max(height[i+1],maxRight[i+1]);
        }
        for(int i=0;i<height.length;i++){
            int minLen=Math.min(maxLeft[i],maxRight[i]);
            if(minLen>height[i]){//如果当前列左边和右边最高中最矮的那一列，都大于大于当前这一列的高度的话
                //说明当前列是下凹的一列，可以存水
                ans+=(minLen-height[i]);//然后找到左边最高和右边最高中，最矮的那一列然后，减去当前列的高度，就是当前列所能储存水的量
            }
        }
        return ans;
    }
}